package codingforgreat.class05;

import java.util.Stack;

//lc 1008
public class Class01_ConstructBinarySearchTreeFromPreorderTraversal {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode bstFromPreorder(int[] preorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        return process(preorder, 0, preorder.length - 1);
    }

    public TreeNode process(int[] arr, int L, int R) {
        if (L > R) {
            return null;
        }
        int firstBig = L + 1;
        for (; firstBig <= R; firstBig++) {
            if (arr[firstBig] > arr[L]) {
                break;
            }
        }
        TreeNode root = new TreeNode(arr[L]);
        root.left = process(arr, L + 1, firstBig - 1);
        root.right = process(arr, firstBig, R);
        return root;
    }
    //最优解，若用数组优化栈结构则为最优
    public TreeNode bstFromPreorder1(int[] preorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        Stack<Integer> stack = new Stack<>();
        int[] help = new int[preorder.length];
        for (int i = 0; i < preorder.length; i++) {
            while(!stack.isEmpty() && preorder[stack.peek()] < preorder[i]){
               int cur = stack.pop();
               help[cur] = i;
            }
            stack.push(i);
        }
        while(!stack.isEmpty()){
            int cur = stack.pop();
            help[cur] = -1;
        }
        return process1(preorder, 0, preorder.length - 1,help);
    }
    public TreeNode process1(int[] arr, int L, int R,int[] help) {
        if (L > R) {
            return null;
        }
        TreeNode root = new TreeNode(arr[L]);
        int firstBig = (help[L] == -1 || help[L] > R ) ? R + 1 : help[L];
        root.left = process1(arr, L + 1, firstBig - 1,help);
        root.right = process1(arr, firstBig, R,help);
        return root;
    }

}
